/*
 * linked_list.cpp
 *
 *  Created on: Jul 20, 2012
 *      Author: hxu
 */
#include "linked_list.h"
#include<iostream>

using namespace std;

linked_list::linked_list(Node* hnode){
	head = hnode;
}

linked_list::linked_list(const string& text){
	const char* new_char = text.c_str();
	char temp_char = new_char[0];
	Node* current_node = NULL;
	int l = text.length();

	head = NULL;

	cout << " Input: " << text << endl;

	for(int i = 0;i<=l-1;i++){
		temp_char = new_char[i];
		if(head==NULL){
			head = new Node(temp_char, NULL);
			current_node = head;
		} else{
			current_node->set_next(new Node(temp_char, NULL));
			current_node = current_node->get_next();
		}
	}
}

linked_list::~linked_list(){
	Node* temp_node = head;
	Node* temp_node2 = NULL;

	// free memory
	while(temp_node!=NULL){
		temp_node2 = temp_node->get_next();
		delete temp_node;
		temp_node = temp_node2;
	}
}

Node* linked_list::get_head() const{
	return head;
}

ostream& operator << (ostream& out, const linked_list& llist){
	const Node* current_node = llist.get_head();
	while(current_node != NULL){
		out << current_node->get_data();
		current_node = current_node->get_next();
	}
	out << endl;

	return out;
}

void linked_list::remove_duplicate(){
	// remove duplicate nodes
	Node* temp_node = head;
	Node* iterator_node = head;
	Node* parent = NULL;

	if(head){
		// non-empty head
		temp_node = head->get_next();
		parent = head;
	}

	while(temp_node!=NULL){
		while(iterator_node!=temp_node){
			if(iterator_node->get_data()==temp_node->get_data()){
				parent->set_next(temp_node->get_next());
				delete(temp_node);
				temp_node = parent->get_next();
				break;
			}else{
				iterator_node = iterator_node->get_next();
			}
		}

		if(iterator_node==temp_node){
			// not duplicated
			parent = temp_node;
			temp_node = temp_node->get_next();
		}

		iterator_node = head;
	}
}

void linked_list::print_n_to_last(int n){
	// print nth to the last elements
	int i=0;
	Node *current_node = head;

	while(i<n-1){
		if(current_node==NULL){
			cout << " " << n << " is larger than the length of the linked list!" << endl;
			return;
		} else{
			current_node = current_node->get_next();
			i++;
		}
	}

	// found the nth node
	while(current_node!=NULL){
		cout << " Element " << i+1 << " is " << current_node->get_data() << endl;
		current_node = current_node->get_next();
		i++;
	}
	cout << " pint_n_to_last finished." << endl;
}

void linked_list::delete_node(Node* node){
	// delete node from list
	Node* next_node = NULL;

	if(node==NULL)
		return;
	else
		next_node = node->get_next();

	if(next_node!=NULL){
		// node is not the last
		node->set_data(next_node->get_data());
		node->set_next(next_node->get_next());
		delete next_node;
	} else{
		// node is the last, delete the last one
		Node* p = head;
		while(p->get_next()!=node){
			// find parent of node
			p = p->get_next();
		}
		p->set_next(NULL);
		delete node;
	}
}